
import java.io.*;
import java.util.Scanner;

public class progTopSort {
    static int numNodes;
    static GraphNode nodes[];
    
    public static void main(String[] args) throws IOException {
       readDigraph();
       topologicalSort(); }
    
    public static void topologicalSort() {
        int       stackCount, 
                  orderedCount = stackCount = 0,
                  inDegrees[] = new int[numNodes];
        GraphNode selected,
                  stack[] = new GraphNode[numNodes],
                  topOrder[] = new GraphNode[numNodes];
        
        //calculate inDegrees
        for (int i = 0; i < numNodes; i++)
            for (int j = 0; j < nodes[i].getOutDegree(); j++)
                inDegrees[nodes[i].getAdjListIndex(j)]++;
        
        //add nodes of inDegree = 0 to stack
        for (int i = 0; i < numNodes; i++)
            if ( 0 == inDegrees[i]) {
                stack[stackCount] = nodes[i];
                stackCount++; }
        
        while (stackCount > 0) {
            //print stack
            System.out.print("stack = [");
            for (int i = 0; i < stackCount-1; i++)
                System.out.print(stack[i].getNodeNumber() + " ");
            System.out.print(stack[stackCount-1].getNodeNumber() + "], node selected = ");
            
            //print selected node, add it to topOrder array, and remove it from stack
            selected = stack[stackCount-1];
            System.out.print(selected.getNodeNumber() + ", topOrder-array = [");
            topOrder[orderedCount] = selected;
            stack[stackCount--] = null; orderedCount++;
            
            //print topOrder array
            for(int i = 0; i < orderedCount-1; i++)
                System.out.print(topOrder[i].getNodeNumber() + " ");
            System.out.println(topOrder[orderedCount-1].getNodeNumber() + "]");
            
            //reduce inDegrees
            for (int j = 0; j < selected.getOutDegree(); j++) {
                inDegrees[selected.getAdjListIndex(j)]--;
                if (0 == inDegrees[selected.getAdjListIndex(j)]) {
                    stack[stackCount] = nodes[selected.getAdjListIndex(j)];
                    stackCount++;
    } } } }
    
    //loads graph data from file
    public static void readDigraph() throws IOException {
        File input = new File("digraph.data");
        Scanner digraph = new Scanner(input).useDelimiter("\\D+");
        
        //if file is not empty
        if (digraph.hasNext()) {
            int nodeNum;
            numNodes = digraph.nextInt(); //System.out.println(numNodes);
            nodes = new GraphNode[numNodes];
            while (digraph.hasNext()) {
                nodeNum = digraph.nextInt();
                nodes[nodeNum] = new GraphNode(nodeNum, digraph.nextInt());
                for (int i = 0; i < nodes[nodeNum].getOutDegree(); i++) 
                    nodes[nodeNum].setAdjListIndex(digraph.nextInt(), i); } }
        else return; 
    } }


